#include "../tools.h"


vector<int> pre;    // 记录每个节点的最大上级
int find(int nid)   // 查找最大上级
{ 
    int root = nid;
    while (pre[root] != root) root = pre[root]; // 根上级的上级是自己

    // 路径压缩 - 将路径上所有点的上级改为最大上级
    int cur_node = nid;
    int curnode = nid;
    while(pre[curnode] != root){
        int tmp = pre[curnode];
        pre[curnode] = root;
        curnode = tmp;
    }
    return root ;
}

// 连接线上的两个点
void join(int a, int b)                                      
{
    int fa = find(a);
    int fb = find(b);
    if(fa != fb) pre[max(fa, fb)] = min(fa, fb);
    cout << a << " " << b << endl;
    show(pre);
}


int main(int argc, char const *argv[])
{
    int num = 4;
    vector<pair<int, int>> routes = {{1,3}, {4,3}};

    pre.resize(num + 1);
    for(int i = 1; i <= num; ++i)
        pre[i] = i;
    show(pre);

    for(auto route: routes){
        join(route.first, route.second);
    }

    show(pre);

    return 0;
}
